# -*- coding: utf-8 -*-
'''
Created on Sepçwdá 29, 2010

@author: kivson
'''
from vo.no import No
from bisect import insort, insort_left, insort_right

class Huffman(object):
    '''
    classdocs
    '''


    def __init__(self, listaNos):
        '''
        Constructor
        '''
        self.listaNos = listaNos
        self.tabela = {}
    

    def extraiTabela(self):
        for cod in self.listaNos[0].codigo():
            self.tabela[cod[0]] = cod[1]

    def arvoriza(self):
        
        self.listaNos.sort()
        while len(self.listaNos) > 1:
            no1 = self.listaNos.pop(0)
            no2 = self.listaNos.pop(0)
            novoNo = No()
            novoNo.esq = no2
            novoNo.dir = no1
            novoNo.quantidade = no1.quantidade + no2.quantidade
            insort_left(self.listaNos, novoNo)
        
        self.extraiTabela()
        
        return
        
if __name__ == '__main__':
    from negocio.parser import Parser
    parser = Parser()
    parser.texto = 'Kivson Marcell nogueira de Andrade !!!'
    l =  parser.parseia()
    huf = Huffman(l)
    
    print huf.listaNos
    huf.arvoriza()
    print huf.tabela
        
